package com.leetcode;

import com.leetcode.common.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 23. 合并K个升序链表
 * 使用优先队列合并
 *
 * @author fy
 * @date 2022-04-17 15:05
 */
public class Solution23_2 {

    public ListNode mergeKLists(ListNode[] lists) {
        // jdk的堆默认为最小堆
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(Comparator.comparingInt((ListNode a) -> a.val));
        for (ListNode list : lists) {
            if (list != null) {
                priorityQueue.offer(list);
            }
        }
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        while (!priorityQueue.isEmpty()) {
            ListNode node = priorityQueue.poll();
            cur.next = node;
            cur = cur.next;
            if (node.next != null) {
                priorityQueue.offer(node.next);
            }
        }
        return dummyHead.next;
    }

}
